import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/13 9:28
 * @description 改进：使用Hash表，哈希表可以在O(1)时间内完成插入和删除操作，但是无法根据下标定位到特定元素
 * 此环境下，使用变长数组和哈希表组合, List存储数组元素，在O(1)时间内获取，HashMap存储每个元素的下标位置，在O(1)时间内插入或删除
 */
public class Solution {
    List<Integer> nums;
    Map<Integer, Integer> indices;
    Random random;

    public Solution(){
        nums = new ArrayList<>();
        indices = new HashMap<>();
        random = new Random();
    }
    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }
    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        int index = indices.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        indices.put(last, index);
        nums.remove(nums.size() - 1);
        indices.remove(val);
        return true;
    }
    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}
